package _01_动态数组;

public class _134_加油站 {

    public static void main(String[] args) {

        _134_加油站 v = new _134_加油站();

        int[] gas = new int[]{2, 3, 4};
        int[] cost = new int[]{3, 4, 3};
        System.out.println(v.canCompleteCircuit(gas, cost));
    }

    public int canCompleteCircuit(int[] gas, int[] cost) {
        int len = gas.length;
        int start = -1;
        for (int i = 0; i < len; i++) {
            // 向找到可以向前走的
            if (gas[i] >= cost[i]) {
                start = i;
                int remain = gas[i] - cost[i];
                int end = len + start;
                while (++i < end) {
                    int mapI = i >= len? i - len: i;
                    remain += gas[mapI];
                    if (remain >= cost[mapI]) {
                        // 可以向前
                        remain -= cost[mapI];
                    } else {
                        start = -1;
                        // 不可以向前
                        break;
                    }
                }
            }
        }
        return start;
    }

}
